package cn.huawei;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/
import java.util.*;

public class Main {
    public static void main(String[] args) {

    }


    public int getMost(int[][] values) {
        if (values == null || values.length == 0 || values[0].length == 0)
            return 0;
        int n = values[0].length;
        int[] dp = new int[n];
        for (int[] value : values) {
            dp[0] += value[0];
            for (int i = 1; i < n; i++)
                dp[i] = Math.max(dp[i], dp[i - 1]) + value[i];
        }
        return dp[n - 1];
    }

    public int GetUglyNumber_Solution(int index) {

        if (index < 7)    return index; // 7也是质因子，前面的数都是丑数
        int[] arr = new int[index];
        arr[0] = 1;
        int t1 = 0, t2 = 0, t3 = 0;
        for (int i = 1; i < index; ++i) {
            arr[i] = Math.min(arr[t1] * 2, Math.min(arr[t2] * 3, arr[t3] * 5));
            if (arr[i] == arr[t1] * 2)    ++t1;
            if (arr[i] == arr[t2] * 3)    ++t2;
            if (arr[i] == arr[t3] * 5)    ++t3;
        }
        return arr[index - 1];
    }

    public int minCut (String s) {
        // write code here
        char[] chs = s.toCharArray();
        int[] dp = new int[chs.length + 1];
        for(int i = 0; i < dp.length; ++i) dp[i] = i - 1;
        for(int i = 0; i < chs.length; ++i) {
            expand(chs, i, i, dp);
            expand(chs, i, i + 1, dp);
        }
        for (int i : dp) {
            System.out.println(i);
        }
        return dp[chs.length];
    }

    private void expand(char[] chs, int i, int j, int[] dp) {
        while(i >= 0 && j < chs.length && chs[i] == chs[j]) {
            dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1);
            --i;
            ++j;
        }
        return;
    }
}
